读书笔记-Redis 数据结构与对象

读书

Redis：数据结构与对象

1. SDS：简单动态字符串（Simple Dynamic String）

在 Redis 里面，C 语言传统的字符只会作为常量，用在一些无须修改的字符串，其他字符串都用 SDS

1
2
3
4
5
6
7
8
9
struct sdshdr {
	// 记录 buf 数组中已使用字节的数量
	// 等于 SDS 所保存字符串的长度
	int len;
	// 记录buf 数组中未使用字节的数量
	int free;
	// 字节数组，用于保存字符串
	char buf[];
}

SDS 与 C 字符串的区别

  1. 获取字符串长度：O(1)， len

    STRLEN key 命令复杂度仅为 O(1)

  2. 杜绝缓冲区溢出：buffer overflow

    SDSCAT（SDS API） 在拼接字符串之前会先检查空间是否足够(free)，不够的话先用 SDS 空间分配策略进行分配，再进行拼接

    APPEND key 永远不会抹掉其他字符串的内存空间

  3. 减少修改字符串时带来的内存重分配次数

    对于修改 C 字符串而言，拼接操作(append)会扩展底层数组的空间大小，截断操作(trim)会释放不再使用的空间，这两种内存重分配操作前者容易引起缓冲区溢出，后者容易引起内存泄漏，为了解决这两个问题，SDS 采用 空间预分配 和 惰性空间释放 两种优化策略

    a. 空间预分配：当 SDS 需要修改并进行空间扩展时，程序不仅会为 SDS 分配修改所必须的空间，还会为 SDS 分配额外的未使用空间(free)

    a.1 分配后 len > 1M，则给 free 预分配 1M 空间

    a.2 分配后 len < 1M，则给 free 预分配 len 空间

通过这种预分配策略，SDS 将连续增长 N 次字符串所需要的内存重分配次数从必定 N 次降低为 最多 N 次

b. 惰性空间释放：当 SDS 需要缩短保存的字符串时，程序不会立即回收多出来的字节，而是使用 free 属性将这些字节数量记录起来，等待再次使用

  4. 二进制安全

    buf 长度是 len，决定了结尾，即使 buf 中存在 ‘\0’，也不会被认为是结束

  5. 兼容部分 C 字符串函数

    strcasecmp(sds->buf，”hello world”)

    strcat(c_string，sds->buf)

2. LinkedList：链表

在 Redis 中，链表建的操作，底层实现之一的数据结构就是链表，除此之外，发布与订阅、慢查询、监视器等功能也用的是链表

链表节点（listNode）：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct listNode {
	
	// 前置节点
	struct listNode *prev;
	
	// 后置节点
	struct listNode *next;
	
	// 节点值
	void *value;

} listNode;

链表（list）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct list {
	
	// 表头节点
	listNode *head;

	// 表尾节点
	listNode *tail;

	// 链表所包含的节点数
	unsigned long len;

	// 节点值复制函数
	void *(*dup) (void *ptr);

	// 节点值释放函数
	void (*free) (void *ptr);

	// 节点值对比函数
	int (*match) (void *ptr);

} list;

Redis 使用 list 结构持有链表，是 双端、无环、带表头指针和表尾指针，带链表长度计数器、多态（void * 接收各种类型的值） 性质的链表

3. Map：字典

在 Redis 中，字典是哈希键的底层实现之一，字典由哈希表实现，哈希表由哈希表节点实现，哈希表节点就是键值对

哈希表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictEntry{
	
	// 键
	void *key;
	
	// 值
	union {
		void *val;
		uint64_t u64;
		int64_t s64;
	} v;
	
	// 指向下个了哈希表节点，形成链表：解决哈希冲突
	struct dictEntry *next;

} dictEntry;

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;

	// 哈希表大小
	unsigned long size;

	// 哈希表大小掩码，用于计算哈希值：等于 size - 1
	unsigned long sizemask;

	// 已有节点数量
	unsigned long used;
	
} dictht;

字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dict {
	
	// 类型特定函数
	dictType *type;

	// 私有数据
	void *privdata;

	// 哈希表：每个字典由两个哈希表，一个平时使用，一个仅在 rehash 时使用
	dictht ht[2];

	// rehash索引
	int trehashidx;

} dict;

其中，type 和 privdata 是针对不同类型的键值对，为创建多态字典而设置，type 是指向 dictType 结构的指针，每个结构保存了一簇用于操作特定类型键值对的函数，比如：不同类型的哈希函数

ht 属性是一个包含两个项的数组，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 当进行 rehash 时使用

Redis 的哈希算法使用的是 MurmurHash

hash = dict -> type -> hashFunction(key)

index = hash & dict -> ht[x].sizemask

Redis 使用链表地址发来解决冲突，新节点将插入链表表头（O(1)）

重新哈希（rehash）操作对哈希表的大小进行相应的扩展或者收缩，维持负载因子（load factor）在一个合理的范围之内，实际上就是 ht[0] 和 ht[1] 相互替代（比如：扩展 ht[1] - 迁移 0->1 - 释放 ht[0]）

load factor = ht[0].used / ht[0].size

哈希表的扩展与收缩的时机

  1. 服务器目前没有执行 BGSAVE 或者 BGREWRITEAOF 命令，并且哈希表的负载因子 >= 1;

  2. 服务器目前正在执行 BGSAVE 或者 BGREWRITEAOF 命令，并且哈希表的负载因子 >= 5;

渐进 rehash：为了避免 rehash 对服务器性能造成影响，服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1]，而是分多次、渐进式的将 ht[0] 里面的键值对慢慢 rehash 到 ht[1]，采用分治的思想，随着操作，随着 rehash，期间新加入的值会直接进入 ht[1]，如果 ht[0] 中 get 不到，会自动去 ht[1] 里面查找

4. Skip List：跳表

  • 跳跃表是有序集合的底层实现之一

  • Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成, 其中 zskiplist 用于保存跳跃表信息（比如表头、表尾节点、长度）, 而 zskiplistNode 则用于表示跳跃表节点

  • 每个跳跃表节点的层高都是 1 至 32 之间的随机数

  • 在同一个跳跃表中, 多个节点可以包含相同的分值, 但每个节点的成员对象必须是唯一的

  • 跳跃表中的节点按照分值大小进行排序, 当分值相同时, 节点按照成员对象的大小进行排序

5. IntSet: 整数集合
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {

	// 编码方式
	uint32_t encoding;

	// 集合包含的元素数量
	uint32_t length;

	// 保存元素的数组
	int8_t contents[];

} intset;

每次加入新的元素，都有可能引发升级: 1. 扩展空间, 2: 类型统一化, 3: 将新元素和老元素统一加入到扩展后的空间, 需要注意的是: 不支持降级

  • 整数集合是集合键的底层实现之一

  • 整数集合的底层实现为数组, 这个数组以有序、无重复的方式保存集合元素, 在有需要时, 程序会根据新添加元素的类型, 改变这个数组的类型

  • 升级操作为整数集合带来了操作上的灵活性, 并且尽可能的节约了内存

  • 整数集合只支持升级操作, 不支持降级操作

6. Zip List: 压缩列表

  • 压缩列表是一种为节约内存而开发的顺序型数据结构

  • 压缩列表被用作列表键和哈希键的底层实现之一

  • 压缩列表可以包含多个节点, 每个节点可以保存一个字节数组或者整数值

  • 添加新节点到压缩列表, 或者从压缩列表中删除节点, 可能会引发连锁更新操作, 但这种操作出现的几率并不高

7. Object: 对象

Redis 并没有直接使用这些数据结构来实现键值对数据库, 而是基于这些数据结构创建了一个对象系统, 这个系统包含 字符串对象、列表对象、哈希对象、集合对象和有序集合对象 五种, 根据命令, 判断哪种对象适合就用于执行

  • Redis 数据库中的每个键值对的键和值都是一个对象

  • Redis 共有字符串、列表、哈希、集合、有序集合五种类型的对象, 每种类型的对象至少都要两种或以上的编码方式, 不同的编码可以在不同的使用场景上优化对象的使用效率

  • 服务器在执行某些命令之前, 会先检查给定键的类型能否执行指定的命令, 而检查一个键的类型就是检查键的值对象的类型

  • Redis 的对象系统带有引用计数实现的内存回收机制

  • Redis 会共享值为 0 到 9999 的字符串对象

  • 对象会记录自己的最后一次被访问的时间, 这个时间可以用于计算对象的空转时间

如需转载，请注明出处